In order to understand what a pseudorandom function generator (PRFG) is, one needs to understand what it means for a function to be random or pseudorandom.
A truly random function
The input to a PRF may sometimes be treated as an integer between $0$ and $2^S - 1$, which can be represented as a binary string of length $S$. In these cases, it is called an *index* instead of an input data block.
The reason that these two notions of a random function are equivalent is that each "coin toss" can be thought of as making a step forward in search for the function
A random function is still *deterministic* in the sense that when input the same data block it will always give the same output.
Unfortunately, truly random functions present a great implementational challenge for classical computers due to their difficulty in obtaining true randomness. A computer cannot really "flip a coin
This is why we have to settle for pseudorandom functions.
A *pseudorandom function* is an efficient algorithm $\textit{PRF}(idb: \mathbf{str}[S]) \to \mathbf{str}[l_{\textit{out}}]$ such that for every efficient distinguisher $D(\textit{func}: \textbf{function<}\mathbf{str}[S] \to \mathbf{str}[l_{\textit{out}}]\textbf{>}) \to \mathbf{bit}$ it holds that
$$\left|\Pr[D(\textit{PRF}) = 1] - \Pr_{H \leftarrow_R \{0,1\}^S \to \{0,1\}^{l_{\text{out}}}}[D(H) = 1]\right| \le \epsilon(S)$$
for some negligible $\epsilon$.
The distinguisher $D(\textit{func}: \textbf{function<}\mathbf{str}[S] \to \mathbf{str}[l_{\text{out}}]\textbf{>}$ takes a function whose inputs are strings of length $S$ and which outputs a string of length $l_{\text{out}}$ and tries to determine if the function is a truly random function. This notation means that the distinguisher has *oracle access* to the function - it can freely query the function with any inputs and can inspect the resulting outputs. Sometimes, the objectively worse notation $D^f(1^S)$ is also used to denote that the distinguisher $D$ has oracle access to the function $f$.
A function is pseudorandom if there is no efficient distinguisher which can tell the difference between it and a truly random function $H$ which was chosen from the uniform distribution of all functions $\{0,1\}^S \to \{0,1\}^{l_{\text{out}}}$ with non-negligible probability.
Pseudorandom functions are useful because they are a generalisation of pseudorandom generators. The length of the output of a PRG must always be greater than the length of its seed, but PRFs allow for an output whose length is independent of the input data block. Mostly, however, they are useful because they produce pseudorandom strings, just like PRGs.
But as with most things in cryptography, it is unknown if pseudorandom functions actually exist. The definition is quite broad in the sense that there should be absolutely no distinguisher which can tell that the function is actually not truly random - a pretty difficult thing to do. So, once again, we are forced to hope that they do exist because otherwise cryptography falls apart - we consider a given algorithm to be a pseudorandom function until someone strings along and proves us wrong. Nevertheless, we still want to make as few assumptions as possible and build the rest on top of it.
There exists a pseudorandom function $\textit{PRF}(idb: \mathbf{str}[S]) \to \mathbf{bit}$ which outputs a single bit, i.e. $l_{\text{out}} = 1$.
As it turns out, such a pseudorandom function can be used to construct PRFs with any output length. TODO
Pseudorandom generators produces pseudorandom strings, while pseudorandom function generators (PRFGs) produce pseudorandom functions.
A *pseudorandom function generator (PRFG)* is an efficient algorithm $\textit{PRFG}(seed: \textbf{str}[S]) \to \textbf{function<}\textbf{str}[S] \to \textbf{str}[l_{\text{out}}]\textbf{>}$ which takes a seed $s \in \{0,1\}^S$ and outputs a pseudorandom function whose input is a data block of size $S$ and whose output is a string of length $l_{\text{out}}$.
A pseudorandom function generator takes a seed and produces a pseudorandom function. The resulting function takes input data blocks with the same length $S$ as the PRFG's seed and its outputs have length $l_{\text{out}}$. It is common to notate a PRF that was produced by PRFG as $f_s$ where $f$ is the function's name and $s$ is the seed used to obtain it.
It is important to remember that the output of a PRFG is a function. Specifically, a PRFG produces a function which takes inputs of the same size as the PRFG's seed. This coincidence has unfortunately led to PRFs and PRFGs commonly being mixed up. It is common to see a PRFG as a two input algorithm
fn PRFG(seed: str[S], idb: str[S]) -> str[l_out] {
let PRF = get_prf_from_seed(seed);
return PRF(idb);
}
Okay but how can we construct a PRFG algorithm? Well, as it turns out a pseudorandom generator can be used to construct such algorithms. In particular, a PRG
We will denote the first
The PRFG begins by invoking the PRG
This can be illustrated by the following tree diagram:
The value
The intuition behind why this is indeed a PRFG is pretty simple - if
TODO